package com.lw.leetcode.bingChaJi.b;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * 684. 冗余连接
 * 剑指 Offer II 118. 多余的边
 *
 * @author liw
 * @version 1.0
 * @date 2022/5/31 17:39
 */
public class FindRedundantConnection {
    public static void main(String[] args) {
        FindRedundantConnection test = new FindRedundantConnection();

        // {2,3}
        int[][] edges = {{1, 2}, {1, 3}, {2, 3}};

        // {1,4}
//        int[][] edges = {{1, 2}, {2, 3}, {3, 4}, {1, 4}, {1, 5}};

        int[] redundantConnection = test.findRedundantConnection(edges);
        System.out.println(Arrays.toString(redundantConnection));
    }

    private int[] arr;

    public int[] findRedundantConnection(int[][] edges) {
        int length = edges.length;
        arr = new int[length + 1];
        Arrays.fill(arr, -1);
        for (int[] edge : edges) {
            int af = find(edge[0]);
            int bf = find(edge[1]);
            if (af == bf) {
                return edge;
            }
            arr[bf] = af;
        }
        return edges[0];
    }

    private int find(int index) {
        int t = arr[index];
        if (t == -1 || t == index) {
            arr[index] = index;
            return index;
        }
        t = find(t);
        arr[index] = t;
        return t;
    }

}
